package bishiqinagxun;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }

  //题目 : 笔试强训  day28 第三题  二叉树中的最大路径和
    //算法  递归
public class Solution {
    private static int maxval = Integer.MIN_VALUE;

    public int maxPathSum (TreeNode root) {
        fun(root);
        return maxval;
    }
    private static int fun(TreeNode root) {
        //递归出口
        if(root == null) {
            return 0;
        }

        int left =fun(root.left);
        int right = fun(root.right);

        maxval = Math.max(maxval,left+right+root.val);
        return Math.max(Math.max(left,right)+root.val,0);
    }
}
